//输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。 
//
// 例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。 
//
// 
//
// 示例： 
//
// 
//给定一个链表: 1->2->3->4->5, 和 k = 2.
//
//返回链表 4->5. 
// Related Topics 链表 双指针 👍 322 👎 0

package com.cute.leetcode.editor.cn;
public class LianBiaoZhongDaoShuDiKgeJieDianLcof {
    public static void main(String[] args) {
        Solution solution = new LianBiaoZhongDaoShuDiKgeJieDianLcof().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    /**
     * 使用两个节点实现，一个先走k步，再一起走
     */
    public ListNode getKthFromEnd(ListNode head, int k) {
        if (k == 0) return null;// 这里K其实不能为0
        ListNode node = head;
        while (node != null && k-- > 0) node = node.next;// node先走k步
        if (k > 0) return null;// 这里说明原来就没K这么多个节点
        ListNode res = head;
        while (node != null){// 然后两个节点一起走，直到node为null
           res = res.next;
           node = node.next;
        }
        return res;
    }

    /**
     * 题目23，Leetcode剑指Offer板块上没有这一题，但是普通题库中有
     * 巡展环形链表中的入口，没有返回null
     * 仍然是使用快慢指针
     */
    public ListNode findCircle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow){
                while (head != fast){ //说明有环存在，结束条件即为相遇节点
                    head = head.next;
                    fast = fast.next;
                }
                return head;
            }
        }
        return null;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
public class ListNode {
    int val;
    ListNode next;
    ListNode(){};
    ListNode(int x) { val = x; }
}

}